import java.util.Arrays;

public class Test {
    // 题目1：二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(right == null) return left;
        if(left == null) return right;
        return root;
    }

    // 题目2：二叉搜索树的最近公共祖先
    // 方法一：递归
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if(p.val >= root.val && q.val <= root.val || p.val <= root.val && q.val >= root.val){
            return root;
        }
        if(p.val < root.val && q.val < root.val){
            return lowestCommonAncestor1(root.left, p, q);
        }
        if(p.val > root.val && q.val > root.val){
            return lowestCommonAncestor1(root.right, p, q);
        }
        return null;
    }
    // 方法二：
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;
        while(true){
            if(p.val > ancestor.val && q.val > ancestor.val){
                ancestor = ancestor.right;
            }else if(p.val < ancestor.val && q.val < ancestor.val){
                ancestor = ancestor.left;
            }else{
                return ancestor;
            }
        }
    }

    // 题目3：二叉搜索树的最小绝对差
    TreeNode pre;
    int ret = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
        dsf(root);
        return ret;
    }
    public void dsf(TreeNode root){
        if(root == null){
            return;
        }
        dsf(root.left);
        if(pre != null){
            ret = Math.min(ret, root.val - pre.val);
        }
        pre = root;
        dsf(root.right);
    }

    // 题目4：
    public static int[] findNum(int[] arr){
        Arrays.sort(arr);
        int i = 0;
        int n = arr.length;
        int[] ret = new int[2];
        int flag = 0;
        while(i < n - 1){
            if(arr[i] == arr[i + 1]){
                i += 2;
            }else{
                if(flag == 0){
                    ret[0] = arr[i];
                    i++;
                    flag=1;
                }
                if(flag == 1){
                    ret[1] = arr[i];
                    i++;
                    break;
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] arr = {1,4,5,5,4,2,3,1};
        int[] ret =findNum(arr);
        for(int i = 0; i < 2; i++){
            System.out.println(ret[i]);
        }
    }
}



